#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*
 * Memory Management Simulation
 * 
 * This program simulates memory allocation and deallocation using different strategies:
 * - First Fit
 * - Best Fit
 * - Worst Fit
 * 
 * Students should implement the TODO sections marked below
 */

#define MEMORY_SIZE 640 // 640KB total memory
#define FREE 0
#define ALLOCATED 1

// Current allocation algorithm
char* current_algorithm = NULL;

// Memory block structure
typedef struct block {
    int id;             // Process ID (0 for free blocks)
    int status;         // FREE or ALLOCATED
    int start_address;  // Start address of the block
    int size;           // Size of the block in KB
    struct block *next; // Pointer to the next block
} Block;

Block *memory_head = NULL;  // Head of the memory block list
int next_id = 1;            // Next process ID to assign

// Function to initialize memory with one large free block
void init_memory() {
    memory_head = (Block *)malloc(sizeof(Block));
    memory_head->id = 0;
    memory_head->status = FREE;
    memory_head->start_address = 0;
    memory_head->size = MEMORY_SIZE;
    memory_head->next = NULL;
}

// Function to display current memory status
void display_memory() {
    Block *current = memory_head;
    printf("\n===== Memory Status =====\n");
    
    printf("\nFree Blocks:\n");
    printf("%-10s %-15s %-10s\n", "Start Addr", "Size (KB)", "Status");
    printf("--------------------------------\n");
    
    current = memory_head;
    int free_count = 0;
    while (current != NULL) {
        if (current->status == FREE) {
            printf("%-10d %-15d %-10s\n", 
                   current->start_address, 
                   current->size, 
                   "FREE");
            free_count++;
        }
        current = current->next;
    }
    if (free_count == 0) {
        printf("No free blocks available\n");
    }
    
    printf("\nAllocated Blocks:\n");
    printf("%-10s %-15s %-10s %-10s\n", "PID", "Start Addr", "Size (KB)", "Status");
    printf("------------------------------------------\n");
    
    current = memory_head;
    int allocated_count = 0;
    while (current != NULL) {
        if (current->status == ALLOCATED) {
            printf("%-10d %-15d %-10d %-10s\n", 
                   current->id, 
                   current->start_address, 
                   current->size, 
                   "ALLOCATED");
            allocated_count++;
        }
        current = current->next;
    }
    if (allocated_count == 0) {
        printf("No allocated blocks\n");
    }
    printf("\n");
}

// TODO 1: Implement the First Fit algorithm
// This algorithm allocates the first free block that is big enough
Block* first_fit(int size) {
    // TODO: Search through the memory blocks and return the first free block 
    // that has size >= requested size
    
    return NULL;  // Return NULL if no suitable block is found
}

// TODO 2: Implement the Best Fit algorithm
// This algorithm allocates the smallest free block that is big enough
Block* best_fit(int size) {
    // TODO: Find the smallest free block that can accommodate the requested size
    
    return NULL;  // Return NULL if no suitable block is found
}

// TODO 3: Implement the Worst Fit algorithm
// This algorithm allocates the largest free block available
Block* worst_fit(int size) {
    // TODO: Find the largest free block available
    
    return NULL;  // Return NULL if no suitable block is found
}

// malloc-like function: my_malloc
void* my_malloc(int size) {
    if (size <= 0) {
        printf("Invalid size requested\n");
        return NULL;
    }
    
    Block *suitable_block = NULL;
    
    // Select allocation algorithm based on user choice
    if (strcmp(current_algorithm, "first") == 0) {
        suitable_block = first_fit(size);
    } else if (strcmp(current_algorithm, "best") == 0) {
        suitable_block = best_fit(size);
    } else if (strcmp(current_algorithm, "worst") == 0) {
        suitable_block = worst_fit(size);
    } else {
        printf("Invalid algorithm specified!\n");
        return NULL;
    }
    
    if (suitable_block == NULL) {
        printf("my_malloc: Failed to allocate %d KB. No suitable block found.\n", size);
        return NULL;
    }
    
    int allocated_pid;
    
    // TODO 4: Implement block allocation logic
    // If the block is exactly the size we need, change its status to ALLOCATED
    // If the block is larger, split it into an allocated block and a free block
    
    // TODO: Your implementation here
    
    return NULL; // Replace with your implementation
}

// free-like function: my_free
void my_free(void* ptr) {
    if (ptr == NULL) {
        printf("my_free: NULL pointer, nothing to free\n");
        return;
    }
    
    // Convert pointer back to PID
    int pid = (int)(long)ptr;
    
    Block *current = memory_head;
    Block *prev = NULL;
    
    // Find the block with the specified PID
    while (current != NULL && !(current->status == ALLOCATED && current->id == pid)) {
        prev = current;
        current = current->next;
    }
    
    if (current == NULL) {
        printf("my_free: PID %d not found in allocated memory.\n", pid);
        return;
    }
    
    printf("my_free: Released %d KB from PID %d\n", current->size, pid);
    
    // TODO 5: Implement block deallocation and merging
    // 1. Change the block status to FREE
    // 2. Merge with adjacent free blocks if possible
    
    // TODO: Your implementation here
}

// Function to list all allocated blocks
void list_allocated_blocks() {
    Block *current = memory_head;
    int count = 0;
    
    printf("\nCurrently Allocated Blocks:\n");
    printf("%-10s %-15s %-10s\n", "PID", "Start Addr", "Size (KB)");
    printf("-----------------------------------\n");
    
    while (current != NULL) {
        if (current->status == ALLOCATED) {
            printf("%-10d %-15d %-10d\n", current->id, current->start_address, current->size);
            count++;
        }
        current = current->next;
    }
    
    if (count == 0) {
        printf("No allocated blocks\n");
    }
    printf("\n");
}

// Interactive mode function
void interactive_mode(char *algorithm) {
    int choice;
    int size;
    int pid;
    
    // Initialize the memory
    init_memory();
    current_algorithm = algorithm;
    
    printf("\n=== Memory Management Simulation with %s Fit Algorithm ===\n", 
           strcmp(algorithm, "first") == 0 ? "First" : 
           strcmp(algorithm, "best") == 0 ? "Best" : "Worst");
    
    printf("Initial state: 640KB free memory\n");
    display_memory();
    
    while (1) {
        printf("\nMemory Management Operations:\n");
        printf("1. Allocate Memory (my_malloc)\n");
        printf("2. Free Memory (my_free)\n");
        printf("3. Display Memory Status\n");
        printf("4. List Allocated Blocks\n");
        printf("5. Exit\n");
        printf("Enter your choice: ");
        
        if (scanf("%d", &choice) != 1) {
            // Clear input buffer if invalid input
            while (getchar() != '\n');
            printf("Invalid input. Please enter a number.\n");
            continue;
        }
        
        switch (choice) {
            case 1: // Allocate memory
                printf("Enter size to allocate (in KB): ");
                if (scanf("%d", &size) != 1 || size <= 0) {
                    printf("Invalid size. Please enter a positive number.\n");
                    while (getchar() != '\n'); // Clear input buffer
                    continue;
                }
                
                void* ptr = my_malloc(size);
                if (ptr != NULL) {
                    printf("Successfully allocated %d KB with PID %d\n", size, (int)(long)ptr);
                }
                display_memory();
                break;
                
            case 2: // Free memory
                list_allocated_blocks();
                printf("Enter PID to free (or 0 to cancel): ");
                if (scanf("%d", &pid) != 1 || pid < 0) {
                    printf("Invalid PID. Please enter a non-negative number.\n");
                    while (getchar() != '\n'); // Clear input buffer
                    continue;
                }
                
                if (pid == 0) {
                    printf("Operation cancelled.\n");
                    continue;
                }
                
                my_free((void*)(long)pid);
                display_memory();
                break;
                
            case 3: // Display memory status
                display_memory();
                break;
                
            case 4: // List allocated blocks
                list_allocated_blocks();
                break;
                
            case 5: // Exit
                printf("Exiting memory management simulation.\n");
                return;
                
            default:
                printf("Invalid choice. Please try again.\n");
        }
    }
}

int main(int argc, char *argv[]) {
    if (argc != 2) {
        printf("Usage: %s [first|best|worst]\n", argv[0]);
        return 1;
    }
    
    char *algorithm = argv[1];
    
    if (strcmp(algorithm, "first") != 0 && 
        strcmp(algorithm, "best") != 0 && 
        strcmp(algorithm, "worst") != 0) {
        printf("Invalid algorithm. Use 'first', 'best', or 'worst'.\n");
        return 1;
    }
    
    interactive_mode(algorithm);
    
    return 0;
}